The present invention relates generally to a processor-based technique in the field of information decoding, and, more particularly, to a process for decoding signals embedded in an acquired image version of an original image. Information about geometric properties of the original image can be determined from the embedded signals in the acquired image thus allowing geometric transformations of the acquired image in order to match geometric properties of the original image, without use of the original image in the decoding or transformation processes.
Encoding information in image form to permit its subsequent electronic decoding is a well-known information processing technique. For example, bar codes explicitly carry encoded information in black and white image form, and are typically used in applications where the obvious and perceptible presence of the encoded information is intended and is not a disadvantage.
Data glyph technology is a category of embedded encoded information that is particularly advantageous for use in image applications that require the embedded data to be robust for decoding purposes yet inconspicuous, or even surreptitious, in the resulting image. Data glyph technology encodes digital information in the form of binary 1's and 0's which are then rendered in the form of distinguishable shaped marks such as very small linear marks. Generally, each small mark represents a digit of binary data; whether the particular digit is a digital 1 or 0 depends on the linear orientation of the particular mark. For example, in one embodiment, marks which are oriented from top left to bottom right may represent a 0, while marks oriented from bottom left to top right may represent a 1. The individual marks are of such a size relative to the maximum resolution of a black and white printing device as to produce an overall visual effect to a casual observer of a uniformly gray halftone area when a large number of such marks are printed together in a black and white image on paper; when incorporated in an image border or graphic, this uniformly gray halftone area does not explicitly suggest that embedded data is present in the document. A viewer of the image could perhaps detect by very close scrutiny that the small dots forming the gray halftone area are a series of small marks which together bear binary information. The uniformly gray halftone area may already be an element of the image, or it may be added to the image in the form of a border, a logo, or some other image element suitable to the nature of the document. For example, U.S. Pat. No. 5,315,098, entitled "Methods and Means for Embedding Machine Readable Digital Data in Halftone Images," discloses techniques for encoding digital data in the angular orientation of circularly asymmetric halftone dot patterns that are written into the halftone cells of digital halftone images.
Research and development efforts have also been directed to techniques for inserting, or embedding, encoded information in black and white images in a manner that hides the embedded information in objects or elements in the image, without adding additional elements or objects, while not causing any degradation or distortion. These techniques may be collectively and generally called document or image marking. U.S. Pat. No. 5,278,400, assigned to the assignee of the present invention and entitled "Multiple Threshold Encoding of Machine Readable Code," discloses a method and apparatus for applying coded data to a substrate and decoding the data where the data are encoded in uniformly sized groups of pixels, called cells. Each cell is encoded by distinctively marking a certain number of the pixels to represent the code, without regard to the position in the cell of a marked pixel. For example, a cell comprised of six pixels each of which may be marked in black or white provides for seven possible black-white combinations of the pixels in the cell; a series of three cells provides for 7.sup.3 possible coded combinations, more than enough to encode the 256 character ASCII character set with only 18 pixels. The characteristics of the marking of each cell are preferably the same to facilitate robustness for decoding purposes.
Another type of image or document marking is known as digital watermarking. A successful digital watermarking technique simultaneously achieves two purposes: first, the technique must produce an embedded signal that is imperceptible to a human viewer so as not to diminish the commercial quality and value of the image being watermarked. At the same time, the embedded signal must be resistant to tampering; removal of the embedded signal defeats the identification purpose of watermarking, and so a successful watermarking technique is typically designed so that attempts to remove the embedded signal cause degradation of the image sufficient to render it commercially less valuable or worthless.
Digital watermarking techniques for text document images may differ from those for use in graphic or scenic images. In text document images, document marking is typically achieved by altering the text formatting in a document, or by altering certain characteristics of textual elements (e.g., characters), in a manner that is both reliably able to be decoded and that is largely indiscernible to a reader. In graphic or scenic images, document marking may be achieved by adding a deterministic signal with a well-defined pattern and sequence in areas of the image that are determined to be insignificant or inconspicuous, such as by toggling the least significant bit.
Brassil et al., in "Electronic Marking and Identification Techniques to Discourage Document Copying" in IEEE Journal on Selected Areas in Communications, Vol. 12, No. 8, October 1995, pp. 1495-1504, disclose three techniques for embedding a unique codeword in a text document image that enables identification of the sanctioned recipient of the document while being largely indiscernible to document readers, for the purpose of discouraging unauthorized text document distribution. The image coding schemes were designed to result in a substantial loss of document presentation quality if successfully removed. The techniques disclosed include line shift coding, word shift coding and feature coding. Use of these techniques in the resulting image is typically not noticeable to a viewer of the image, and text in the image is not substantively altered.
PCT International Application WO 95/14289 discloses a signal encoding technique in which an identification code signal is impressed on a carrier to be identified (such as an electronic data signal or a physical medium) in a manner that permits the identification signal later to be discerned and the carrier thereby identified. The method and apparatus are characterized by robustness despite degradation of the encoded carrier, and by holographic permeation of the identification signal throughout the carrier. The embedding of an imperceptible identification code throughout a source signal is achieved by modulating the source signal with a small noise signal in a coded fashion; bits of a binary identification code are referenced, one at a time, to control modulation of the source signal with the noise signal. A preferred embodiment is disclosed which uses identification signals that are global (holographic) and which mimic natural noise sources, thereby allowing the maximization of identification signal energy. In a disclosed preferred embodiment, an N-bit identification word is embedded in an original image by generating N independent random encoding images for each bit of the N-bit identification word, applying a mid-spatial-frequency filter to each independent random encoding image to remove the lower and higher frequencies, and adding all of the filtered random images together that have a "1" in their corresponding bit value of the N-bit identification word; the resulting image is the composite embedded signal. As disclosed at pg. 11 of the application, the composite embedded signal is added to the original image using a formula (Equations 2 and 3) based on the square root of the innate brightness value of a pixel. Varying certain empirical parameters in the formula allows for visual experimentation in adding the composite identification signal to the original image to achieve a resulting marked image, which includes the composite identification signal as added noise, that is acceptably close to the original image in an aesthetic sense. The disclosure notes that the use of a noise, or random, source for the identification signal is optional, and that a variety of other signal sources can be used, depending on application-dependent constraints (e.g., the threshold at which the encoded identification signal becomes perceptible.) In many instances, the level of the embedded identification signal is low enough that the identification signal need not have a random aspect; it is imperceptible regardless of its nature. It is further pointed out, however, that a pseudo random source is usually desired because it is more likely to provide an identification signal that is both detectable and imperceptible in a given context.
Cox, Kilian, Leighton and Shamoon, in NEC Research Institute Technical Report No. 95-10 entitled "Secure Spread Spectrum Watermarking for Multimedia," disclose a frequency domain digital watermarking technique for use in audio, image, video and multimedia data which views the frequency domain of the data (image or sound) signal to be watermarked as a communication channel, and correspondingly, views the watermark as a signal that is transmitted through it. Attacks and unintentional signal distortions are thus treated as noise to which the immersed signal must be immune. To avoid perceptual degradation of the signal, Cox et. al propose to insert the watermark into the spectral components of the data using techniques analogous to spread spectrum communications, hiding a narrow band signal in a wideband channel that is the data. Their technique proposes to spread the watermark over very many frequency bins so that the energy in any one bin is very small and certainly undetectable, on the premise that a watermark that is well placed in the frequency domain of an image or of a sound track will be practically impossible to see or hear if the energy in the watermark is sufficiently small in any single frequency coefficient. At the same time, they propose that the watermark be placed in perceptually significant components of a signal if it is to be robust to common signal distortions and malicious attack, on the premise that significant tampering with these perceptually significant frequencies will destroy the fidelity of the original signal well before the watermark. In particular with respect to watermarking an N.times.N black and white image, the technique first computes the N.times.N DCT of the image to be watermarked,; then a perceptual mask is computed that highlights the perceptually significant regions in the spectrum that can support the watermark without affecting perceptual fidelity. Each coefficient in the frequency domain has a perceptual capacity defined as a quantity of additional information that can be added without any (or with minimal) impact to the perceptual fidelity of the data. The watermark is placed into the n highest magnitude coefficients of the transform matrix excluding the DC component. For most images, these coefficients will be the ones corresponding to the low frequencies. In a disclosed example, the 1000 largest coefficients of the DCT (excluding the DC term) were used. The precise magnitude of the added watermark signal is controlled by one or more scaling parameters that appear to be empirically determined. Cox et. al note that to determine the perceptual capacity of each frequency, one can use models for the appropriate perceptual system or simple experimentation, and that further refinement of the method would identify the perceptually significant components based on an analysis of the image and the human perceptual system. Cox et. al also provide what appears to be a detailed survey of previous work in digital watermarking.
Many of the existing techniques for embedding information in images appear to operate in the black and white image domain, and so do not explicitly address how to embed a signal in a color image that is imperceptible to a human viewer and that does not distort the quality of the image. Digital watermarking techniques, even those that may apply to color images, are typically designed to be irreversible; they produce a tamper-proof embedded signal which cannot be removed without distorting the information in the image; the watermarked image must remain watermarked for all subsequent uses. Moreover, the detection of an embedded identification signal in a watermarked image typically requires the use of the original image, which is typically maintained in a secure location for such future use as needed. While these characteristics of digital watermarking are useful features for image authentication and identification purposes, they may be limitations for other purposes. There are a variety of other image processing applications, especially in the burgeoning field of color image processing, that could make use of a technique for modifying a color image to have an imperceptible signal added thereto, where the modified color image does not have all of the aforementioned limitations of a watermarked image. The present invention addresses this need.